上一章認識 Graph 之後，我已經知道可以透過 Vertex（頂點） 和 Edge（邊） 表示資料之間的關係。

不過昨天都是先理解 Graph 是怎麼畫出來，今天開始遇到另一個問題：

畫在紙上的圓圈和線，程式要怎麼知道誰跟誰相連？

查了一下才發現，Graph 常見的表示方式有兩種：

• Adjacency List（相鄰串列）
• Adjacency Matrix（相鄰矩陣）

Adjacency List：記錄每個 Vertex 的 Neighbor

Adjacency List 的概念就是：每個 Vertex 分別記錄自己有哪些 Neighbor（相鄰節點）。

圖片來源：iThome－圖論 Graph

一開始看到圖片右邊一個接一個，它真正表達的是：

Vertex 1 的 Neighbor 有 2、3、4。

如果今天是一張無向圖：

1 —— 2

因為 Edge 沒有方向，所以 1 的 Neighbor 會有 2，同時 2 的 Neighbor 也會有 1。

但換成有向圖就不一樣：

圖片來源：iThome－圖論 Graph

如果是 1 → 3，只代表可以從 1 前往 3，不代表 3 可以回到 1，所以記錄 Neighbor 時也必須考慮 Edge 的方向。

Adjacency Matrix：像一張速查表

另一種方式是 Adjacency Matrix，我自己覺得它很像一張「速查表」，透過二維矩陣記錄 Vertex 之間有沒有 Edge。

圖片來源：GeeksforGeeks－Graph and its Representations

以沒有 Weight 的 Graph 來說，可以先簡單使用 0 和 1 表示：

• 0：兩個 Vertex 之間沒有 Edge
• 1：兩個 Vertex 之間有 Edge

例如想知道 Vertex 0 和 2 有沒有 Edge，只要查看 [0][2]，如果是 1，就代表兩者直接相連。

無向圖因為 Edge 沒有方向，所以 [0][2] 和 [2][0] 會有相同的結果；但換成有向圖，就不一定會對稱。

圖片來源：GeeksforGeeks－Adjacency Matrix

那兩種表示方式有什麼差別？

一開始我以為 Adjacency List 和 Adjacency Matrix 只是同一張 Graph 的兩種寫法，後來才發現：要選哪一種，還要看 Edge 的多寡，以及程式最常需要進行什麼操作。

如果 Vertex 很多，但 Edge 很少，也就是所謂的 Sparse Graph（稀疏圖），使用 Matrix 會產生大量的 0，這時 Adjacency List 通常會比較省空間。

相反地，如果程式經常需要問：

Vertex 1 和 Vertex 5 有沒有直接相連？

Matrix 就可以直接查看 [1][5]，不用再從 Neighbor 裡一個一個尋找。

那我的專案要用哪一種？

了解 Adjacency List 和 Adjacency Matrix 的差別後，回到我的演算法視覺化平台，目前比較需要知道的是：

「這個 Vertex 可以前往哪些 Neighbor？」

所以接下來我會先使用 Adjacency List 來表示 Graph。

假設有一張簡單的無向圖：

1 —— 2
|
3 —— 4

可以先把每個 Vertex 的 Neighbor 列出來：

1 → 2、3
2 → 1
3 → 1、4
4 → 3

再把這個關係轉換成 TypeScript：

const graph = {
  1: [2, 3],
  2: [1],
  3: [1, 4],
  4: [3],
}

這樣看就簡單多了：

Object 的 Key 代表 Vertex，Array 則記錄這個 Vertex 的 Neighbor。

例如：

1: [2, 3]

就代表 Vertex 1 分別和 2、3 相連。

不過目前我們只記錄了「誰跟誰相連」。

如果每條 Edge 的距離都不一樣，或是從起點到終點有很多條路時，到底怎麼知道哪一條比較短？

這就是下一章要繼續研究的 Weight（權重）與 Shortest Path（最短路徑）。

參考資料

• iThome－圖論 Graph
• GeeksforGeeks－Adjacency List Meaning & Definition in DSA
• GeeksforGeeks－Graph and its Representations
• GeeksforGeeks－Adjacency Matrix